#include "common.h"
namespace common {
void dfsParenthesis(std::string sys, int left, int right, const int n,
                    std::vector<std::string> &cache) {
    if (left > n || right > n || right > left)
        return;
    if (left == n && right == n) {
        cache.push_back(sys);
        return;
    }
    dfsParenthesis(sys + "(", left + 1, right, n, cache);
    dfsParenthesis(sys + ")", left, right + 1, n, cache);
    return;
}
std::vector<std::string> generateParenthesis(int n) {
    std::vector<std::string> cache;
    dfsParenthesis("", 0, 0, n, cache);
    return cache;
}
} // namespace common
